package com.study.s08.shellsort;

public class ShellSort {
	
	/**
	 * 排序方法
	 */
	public static void sort(long[] array) {
		//初始化间隔
		int h = 1;
		//计算最大间隔
		while (h < array.length / 3) {
			h = h * 3 + 1;
		}
		
		while(h > 0) {
			//插入排序
			long tmp = 0;
			for (int i = h; i < array.length; i++) {
				tmp = array[i];
				int j = i;
				while(j > h - 1 && array[j - h] >= tmp) {
					array[j] = array[j - h];
					j -= h;
				}
				array[j] = tmp;
			}
			//减小间隔
			h = (h - 1) / 3;
		}
	}
}
